package com.yequan.leetcode.use.minimumLengthEncoding_820;


import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * //给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。
 * //
 * // 例如，如果这个列表是 ["time", "me", "bell"]，我们就可以将其表示为 S = "time#bell#" 和 indexes = [0,
 * // 2, 5]。
 * //
 * // 对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 "#" 结束，来恢复我们之前的单词列表。
 * //
 * // 那么成功对给定单词列表进行编码的最小字符串长度是多少呢？
 * //
 * //
 * //
 * // 示例：
 * //
 * // 输入: words = ["time", "me", "bell"]
 * //输出: 10
 * //说明: S = "time#bell#" ， indexes = [0, 2, 5] 。
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 1 <= words.length <= 2000
 * // 1 <= words[i].length <= 7
 * // 每个单词都是小写字母 。
 * //
 * //
 *
 * @author : Administrator
 * @date : 2020/3/28
 */
public class MinimumLengthEncoding {

    public static void main(String[] args) {
        String[] words = new String[]{"time", "me", "bell"};

        MinimumLengthEncoding minimumLengthEncoding = new MinimumLengthEncoding();
        int length = minimumLengthEncoding.minimumLengthEncoding1(words);
        System.out.println(length);
    }

    /**
     * 暴力法:
     * 原理: 只要单词表中任意一个单词不是其他某个单词的后缀,则该单词保留
     * 1. 将所有单词存入set集合中
     * 2. 遍历所有单词,且对每一个单词进行取后缀操作,将取出的后缀字符串与set集合中的对比,有一样的则删除该字符串
     * 3. 将set集合遍历,长度等于剩余每一个单词加上一个#的长度(加1)
     *
     * @param words
     * @return
     */
    public int minimumLengthEncoding1(String[] words) {
        Set<String> good = new HashSet<>(Arrays.asList(words));
        int length = 0;
        for (String word : words) {
            for (int i = 1; i < word.length(); i++) {
                good.remove(word.substring(i));
            }
        }
        for (String s : good) {
            length += s.length() + 1;
        }
        return length;
    }

}
